/**
    MVP Tree data structure using graph database for I/O storage
    Copyright (C) 2014  David G. Starkweather

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

    David Starkweather starkd88@gmail.com
**/

package org.phash.mvptree;

import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Direction;
import org.neo4j.graphdb.Relationship;
import org.neo4j.graphdb.Transaction;
import java.util.Vector;
import java.util.Collection;
import java.util.ArrayList;
import java.util.Arrays;
import java.io.PrintStream;

enum ComparatorType {
    LESS_THAN, GREATER_THAN
}


/**
 * Main class for mvp tree data structure.
 **/
public class MVPTree {

    private final NodeFactory nf;

    /**
     * ctor to create MVPTree object
     *
     * @param nodeFactory - NodeFactory instance object 
     *
     **/

    public MVPTree(NodeFactory nodeFactory){

	this.nf = nodeFactory;

    }

    /**
     * Get node factory for this tree. An auxiliary class
     * to allow creating datapoints for the tree.
     * @return NodeFactory
     **/
    public NodeFactory getNodeFactory(){

	return nf;

    }

    /**
     * shut down the mvptree. Call when done with the tree.
     *
     **/
    public void shutdown(){
	nf.shutdown();
    }


    /** 
     * Get number of data points stored in tree.
     * @return int
     **/
    public int getPointCount(){

	return nf.getPointCount();

    }

    /**
     * remove a data point by its string id
     * @param id ident of point
     **/
    public void removePoint(String id){

	nf.deletePoint(id);

    }

    /**
     * lookup data point by its string ident.
     * @param id ident of datapoint.
     * @return Datapoint object.
     **/
    public Datapoint lookupPoint(String id){

	return nf.lookupPoint(id);

    }

    private ArrayList<Datapoint> selectVantagePoints(ArrayList<Datapoint> points){
	// select the vantage points for a given node from a list of points.
	ArrayList<Datapoint> vps = new ArrayList<Datapoint>(nf.getNL());
	Datapoint vp = points.remove(0);

	// choose first in list as first vp
	vps.add(points.remove(0));

	while (vps.size() < nf.getNL() && points.size() > 0){

	    // find point furthest from last chosen vp
	    float max_distance = 0.0f;
	    int max_index = 0;
	    for (int i=0;i<points.size();i++){
		float dist =  vp.distance(points.get(i));
		if (dist > max_distance){
		    max_distance = dist;
		    max_index = i;
		}
	    }

	    vp = points.remove(max_index);
	    vps.add(vp);
	}
	
	return vps;
    }

    private ArrayList<Datapoint> getVantagePoints(MVPInternal node){
	// retrieve the vantage points for a given node
	ArrayList<Datapoint> vps = new ArrayList<Datapoint>(nf.getNL());
	for (int i=0;i<nf.getNL();i++){
	    Datapoint vp = node.getVantagePoint(i, nf);
	    if (vp != null){
		vps.add(vp);
	    }
	}
	return vps;
    }

    private void markPointsWithDistances(ArrayList<Datapoint> vps, ArrayList<Datapoint> points, int level){
	// mark a datapoint with its distance to a given vantage point, vp at a given level in 
	// the tree
	int maxPL = nf.getPL();
	for (int i=0;i<vps.size();i++){
	    if (level+i < maxPL){
		Datapoint vp = vps.get(i);
		for (int j=0;j<points.size();j++){
		    Datapoint pnt = points.get(j);
		    float dist = vp.distance(pnt);
		    pnt.setPathDistance(level+i, dist);
		}
	    }
	}
    }

    private float[] calcSplitPoints(Datapoint vp, ArrayList<Datapoint> points){
	// calculate split points, splits[bf-1] to divide a list of points by its distance from
	// a vantage point, vp

	int lengthM = nf.getBF()-1;
	
	float[] dists = new float[points.size()];
	for (int i=0;i<points.size();i++){
	    dists[i] = vp.distance(points.get(i));
	    if (dists[i] < 0 || Float.isNaN(dists[i]))
		throw new BadDistanceValueException();
	}
	Arrays.sort(dists);
	double binSize = (double)points.size()/(double)nf.getBF();
	float[] M = new float[lengthM];
	for (int i=0;i<lengthM;i++){
	    double pos = (i+1)*binSize;
	    int pos1 = (points.size() > 1) ? (int)Math.ceil(pos) : 0;
	    int pos2 = (points.size() > 1) ? (int)Math.floor(pos) : 0;
	    M[i] = (dists[pos1] + dists[pos2])/2.0f;
	}
	return M;
    }


    private ArrayList<Datapoint> cullPoints(Datapoint vp,ArrayList<Datapoint> points,float split, ComparatorType comp){
	// cull points from points according to distance from vp, vantage point, 
	// using 'less than' or 'greater than' relational operand, compe
	ArrayList<Datapoint> culledPoints = new ArrayList<Datapoint>();

	int i=0;
	while (i < points.size()){
	    float distance = vp.distance(points.get(i));
	    if (distance < 0.0f || Float.isNaN(distance)) 
		throw new BadDistanceValueException();
	    if (comp == ComparatorType.LESS_THAN){
		if (distance <= split){
		    culledPoints.add(points.remove(i));
		} else {
		    i++;
		}
	    } else {
		if (distance > split){
		    culledPoints.add(points.remove(i));
		} else {
		    i++;
		}
	    }
	}

	return culledPoints;
    }

    private MVPInternal createInternalNode(ArrayList<Datapoint> points){
	MVPInternal node = nf.createInternalNode();
	ArrayList<Datapoint> vps = selectVantagePoints(points);
	for (int i=0;i<vps.size();i++){
	    node.setVantagePoint(vps.get(i), i);
	}
	return node;
    }


    private MVPLeaf createLeafNode(ArrayList<Datapoint> points){
	MVPLeaf leaf = nf.createLeafNode();
	leaf.addDatapoints(points);
	return leaf;
    }

    private void expandNode(MVPNode node, ArrayList<MVPNode> childNodes){
	int fanout = (int)Math.pow(nf.getBF(), nf.getNL());
	if (node == null || node instanceof MVPLeaf){
	    for (int i=0;i<fanout;i++){
		childNodes.add(null);
	    }
	} else if (node instanceof MVPInternal){
	    MVPInternal internal = (MVPInternal)node;
	    for (int i=0;i<fanout;i++){
		MVPNode child = internal.getChildNodeAt(i);
		childNodes.add(child);
	    }
	}
    }

    private void collatePoints(MVPInternal node, ArrayList<Datapoint> points, 
                               Vector<ArrayList<Datapoint>> childpoints, 
                               int level, int index){
	
	Vector<ArrayList<Datapoint>> pnts = new Vector<ArrayList<Datapoint>>(1);
	pnts.add(points);

	ArrayList<Datapoint> vps = getVantagePoints(node);
	int bf = nf.getBF();
	int nl = nf.getNL();
	int lengthM = bf - 1;
	int fanout = (int)Math.pow(bf, nl);
	int n=0;
	do {
	    int nbchildnodes = (int)Math.pow(bf, n+1);
	    Vector<ArrayList<Datapoint>> pnts2 = new Vector<ArrayList<Datapoint>>(nbchildnodes);
	    for (int i=0;i<nbchildnodes;i++){
		pnts2.add(new ArrayList<Datapoint>());
	    }

	    int nodeIndex = 0;
	    int lengthMn = (nf.getBF()-1)*(int)Math.pow(nf.getBF(), n);
	    float[] msplits = node.getSplitsAt(n);
	    boolean doCalcSplits = false;
	    if (msplits == null){
		msplits = new float[lengthMn];
		doCalcSplits = true;
	    } else {
		doCalcSplits = false;
	    }
	    for (ArrayList<Datapoint> list : pnts){
		float[] mtemp = null;
		if (doCalcSplits){
		    mtemp = calcSplitPoints(vps.get(n), list);
		} else {	
		    mtemp = Arrays.copyOfRange(msplits, nodeIndex*lengthM, nodeIndex*lengthM + lengthM);
		}

		for (int j=0;j<lengthM;j++){
		    ArrayList<Datapoint> culledpts = cullPoints(vps.get(n), list, mtemp[j], ComparatorType.LESS_THAN);
		    pnts2.get(nodeIndex*bf+j).addAll(culledpts);
		    msplits[nodeIndex*lengthM + j] = mtemp[j];
		}

		ArrayList<Datapoint> culledpts = cullPoints(vps.get(n), list, mtemp[lengthM-1], ComparatorType.GREATER_THAN);
		pnts2.get(nodeIndex*bf+bf-1).addAll(culledpts);
		nodeIndex++;
	    }
	    node.setSplitsAt(n, msplits);
	    pnts = pnts2;
	    n++;
	} while (n < nf.getNL());

	for (int i=0;i<fanout;i++){
	    childpoints.get(index*fanout+i).addAll(pnts.get(i));
	}
    }

    private void linkNodes(ArrayList<MVPNode> nodes, ArrayList<MVPNode> childnodes){
	int fanout = (int)Math.pow(nf.getBF(), nf.getNL());
	for (int i=0;i<nodes.size();i++){
	    MVPNode node = nodes.get(i);
	    if (node instanceof MVPInternal){
		MVPInternal internal = (MVPInternal)node;
		for (int j=0;j<fanout;j++){
		    MVPNode child = childnodes.get(i*fanout+j);
		    internal.setChildNodeAt(child, j);
		}
	    }
	}
    }

  

    private MVPNode processNode(int level, int index, MVPNode node, ArrayList<Datapoint> points, 
                                    ArrayList<MVPNode> childNodes, Vector<ArrayList<Datapoint>> childpoints){
	MVPNode retnode = node;
	if (node == null){        //create node 
	    if (points.size() > nf.getLC() + nf.getNL()) {           // create internal node
		MVPInternal internal = createInternalNode(points);
		markPointsWithDistances(getVantagePoints((MVPInternal)internal), points, level);
		collatePoints(internal, points, childpoints, level, index);
		retnode = internal;
	    } else if (points.size() > 0){                          // create leaf node
		MVPLeaf leaf = createLeafNode(points);
		retnode = leaf;
	    }
	} else {                 // node exists 
	    if (node instanceof MVPInternal){               // internal node 
		markPointsWithDistances(getVantagePoints((MVPInternal)node), points, level);
		collatePoints((MVPInternal)node, points, childpoints, level, index);
	    } else if (node instanceof MVPLeaf){            // leaf node
		MVPLeaf leaf = (MVPLeaf)node;
	        int nbExistingPoints = leaf.getPointCount();
		if (points.size() + nbExistingPoints > nf.getLC() + nf.getNL()){ // convert leaf to internal node
		    // extract and keep ALL vantage points
		    // extract only active and non-null leaf points
		    for (int i=0;i<nbExistingPoints;i++){
			Datapoint pnt = leaf.getDatapoint(i, nf);
			if (pnt != null){
			    if (pnt.isActive()){
				points.add(pnt);
			    } else {
				pnt.delete();
			    }
			}
		    }

		    leaf.delete();

		    if (points.size() > nf.getLC() + nf.getNL()){
			MVPInternal internal = createInternalNode(points);
			markPointsWithDistances(getVantagePoints(internal), points, level);
			collatePoints(internal, points, childpoints, level, index);
			retnode = internal;
		    } else { // in case inactive or null datapoints reduce no. points to below leaf capacity
			MVPLeaf newleaf = createLeafNode(points);
			retnode = newleaf;
		    }
		} else if (points.size() > 0){// add to existing leaf 
		    leaf.addDatapoints(points);
		}
	    }
	}
	expandNode(retnode, childNodes);
	return retnode;
    }

    /**
     * add datapoints to tree. List will be emptied on return.
     * @param points list of Datapoint's.
     * 
     **/
    public void addPoints(ArrayList<Datapoint> points){
	MVPNode topnode = nf.getTopNode();
	ArrayList<MVPNode> previousnodes = null;
	ArrayList<MVPNode> currentnodes = new ArrayList<MVPNode>();
	currentnodes.add(topnode);
	int nbnodes = 1;
	Vector<ArrayList<Datapoint>> pnts = new Vector<ArrayList<Datapoint>>();
	pnts.add(points);
	int n = 0;
	int fanout = (int)Math.pow(nf.getBF(), nf.getNL());
	boolean done = true;

	nf.indexPoints(points);
	do {
	    int nbchildnodes = (int)Math.pow(nf.getBF(), n+nf.getNL());
	    done = true;
	    ArrayList<MVPNode> childnodes = new ArrayList<MVPNode>(nbchildnodes);
	    Vector<ArrayList<Datapoint>> pnts2 = new Vector<ArrayList<Datapoint>>(nbchildnodes);
	    for (int i=0;i < nbchildnodes;i++){
		pnts2.add(new ArrayList<Datapoint>());
	    }
	    
	    for (int index=0;index < currentnodes.size(); index++){ 
		MVPNode node = currentnodes.get(index);
		MVPNode newnode = processNode(n, index, node, pnts.get(index), childnodes, pnts2);
		if (newnode != null && !newnode.isSameAs(node)){
		    currentnodes.remove(index);
		    currentnodes.add(index, newnode);
		    if (n == 0){
			newnode.setAsTop();
		    }
		}
	    }
		
	    if (previousnodes != null) linkNodes(previousnodes, currentnodes);

	    previousnodes = currentnodes;
	    currentnodes = childnodes;
	    pnts = pnts2;
	    nbnodes = nbchildnodes;
	    n = n + nf.getNL();

	    // check for end condition 
	    for (ArrayList<Datapoint> list : pnts2){
		if (list.size() > 0){
		    done = false;
		}
	    }
	} while (!done);
    }

    /** print a copy of the tree. 
     *
     **/
    public void printTree(PrintStream strm){
	MVPNode topnode = nf.getTopNode();
	ArrayList<MVPNode> currentnodes = new ArrayList<MVPNode>();
	currentnodes.add(topnode);
	
	int n=0;
	int nbnodes = 1;
	boolean done = true;
	strm.printf("------------------------------\n");
	strm.printf("---------Print----------------\n");
	do {
	    strm.printf("n=%d\n", n);
	    done = true;
	    int nbchildnodes = (int)Math.pow(nf.getBF(), n+nf.getNL());
	    ArrayList<MVPNode> childnodes = new ArrayList<MVPNode>(nbchildnodes);
	    
	    for (int index=0;index<currentnodes.size();index++){
		MVPNode node = currentnodes.get(index);
		if (node != null){
		    if (node instanceof MVPInternal){
			MVPInternal internalnode = (MVPInternal)node;
			for (int i=0;i<nf.getNL();i++){
			    float[] splits = internalnode.getSplitsAt(i);
			    Datapoint vp = internalnode.getVantagePoint(i,nf);
			    strm.printf("(level%d) internal vp%d=%s ", n, i, vp.getId());
			    for (int j=0;j<splits.length;j++){
				strm.printf(" M[%d]=%f ", j, splits[j]); 
			    }
			    strm.printf("\n");
			}
		    } else if (node instanceof MVPLeaf){ 
			MVPLeaf leaf = (MVPLeaf)node;
			int count = leaf.getPointCount();
			strm.printf("(level%d) leaf - %d points\n", n, count);
			for (int i=0;i<count;i++){
			    Datapoint pnt = leaf.getDatapoint(i, nf);
			    strm.printf("    point[%d]=%s\n", i, pnt.getId());
			}
		    } 
		} else {
		    strm.printf("(level%d) null", n);
		}
		strm.printf("\n");
		strm.println("----------------------------------------");
		    
		expandNode(node, childnodes);
	    }
	    
	    currentnodes = childnodes;
	    n = n + nf.getNL();
	    nbnodes = nbchildnodes;

	    for (MVPNode node : currentnodes){
		if (node != null){
		    done = false;
		    break;
		} 
	    }
	} while (!done);
    }

    /**  
     * collect stats of tree
     **/
    public MVPStats stat(){
	MVPNode topnode = nf.getTopNode();
	ArrayList<MVPNode> currentnodes = new ArrayList<MVPNode>();
	currentnodes.add(topnode);

	MVPStats stats = new MVPStats();
	
	int n=0;
	int nbnodes = 1;
	boolean done = true;
	do {
	    done = true;
	    int nbchildnodes = (int)Math.pow(nf.getBF(), n+nf.getNL());
	    ArrayList<MVPNode> childnodes = new ArrayList<MVPNode>(nbchildnodes);
	    
	    for (int index=0;index<currentnodes.size();index++){
		MVPNode node = currentnodes.get(index);
		if (node != null){
		    if (node instanceof MVPInternal){
			stats.nbinternals++;
			stats.nbvps += nf.getNL();
		    } else if (node instanceof MVPLeaf){ 
			MVPLeaf leaf = (MVPLeaf)node;
			stats.nbleafs++;
			stats.nbdatapoints += leaf.getPointCount();
		    }
		}
		expandNode(node, childnodes);
	    }
	    
	    currentnodes = childnodes;
	    n = n + nf.getNL();
	    nbnodes = nbchildnodes;

	    stats.height += 1;
	    for (MVPNode node : currentnodes){
		if (node != null){
		    done = false;
		    break;
		} 
	    }
	} while (!done);

	stats.nblevels = n;
	return stats;
    }

    
    private void addToList(Datapoint pnt, ArrayList<Datapoint> results, ArrayList<Float> qdists, float distance){
	// add point, pnt to results list in order given by qdists array.  'distance' parameter is the distance of 
        // pnt to target.  
	boolean done  = false;
	for (int i=0;i<qdists.size();i++){
	    if (distance <= qdists.get(i)){
		results.add(i, pnt);
		qdists.add(i, distance);
		done = true;
		break;
	    }
	}
	if (!done){
	    results.add(pnt);
	    qdists.add(distance);
	}
    }

    private void checkNode(MVPNode node, Datapoint target, ArrayList<Datapoint> results, 
			   ArrayList<Float> targetdists, ArrayList<Float> qdists, float radius, 
                           ArrayList<MVPNode> childnodes, int level){
	
	int fanout = (int)Math.pow(nf.getBF(), nf.getNL());
	if (node instanceof MVPInternal){
	    MVPInternal internalnode = (MVPInternal)node;
	    ArrayList<Datapoint> vps = getVantagePoints(internalnode);
	    for (int i=0;i<vps.size();i++){
		Datapoint vp = vps.get(i);
		float dist = target.distance(vp);
		if (vp.isActive() && dist <= radius){
		    addToList(vp, results, qdists, dist);
		}
		targetdists.add(level+i, dist);
	    }
    
	    boolean[] currentmarks = { true };
	    int lengthM = nf.getBF() - 1;
	    int n=0;
	    do {
		int nbchildnodes = (int)Math.pow(nf.getBF(), n+1);
		boolean[] childmarks = new boolean[nbchildnodes];
		Arrays.fill(childmarks, false);
		float[] msplits = internalnode.getSplitsAt(n);
		
		int i = 0;
		for (Boolean nodeflag : currentmarks){
		    if (nodeflag){
			float tdist = targetdists.get(level+n);
			float split = msplits[0];
			for (int j=0;j < lengthM;j++){
			    split = msplits[i*lengthM+j];
			    if (tdist - radius <=  split){
				childmarks[i*nf.getBF()+j] = true;
			    }
			}
			split = msplits[i*lengthM+lengthM-1];
			if (tdist + radius >= split){
			    childmarks[i*nf.getBF() + nf.getBF() - 1] = true;
			}
			
		    }
		    i++;
		}
		currentmarks = childmarks;
		n++;
	    } while (n < nf.getNL());
	    
	    for (int i=0;i < fanout;i++){
		if (currentmarks[i]) {
		    MVPNode child = internalnode.getChildNodeAt(i);
		    childnodes.add(child);
		} else {
		    childnodes.add(null);
		}
	    }
	} else if (node instanceof MVPLeaf){
	    MVPLeaf leaf = (MVPLeaf)node;
	    int nbpointsInLeaf = leaf.getPointCount();
	   
	    // check each datapoint in leaf
	    for (int i=0;i<nbpointsInLeaf;i++){
		Datapoint pnt = leaf.getDatapoint(i, nf);
		if (pnt != null && pnt.isActive()){
		    // filter by datapoints distances to every vantage point
		    boolean includePoint = true;
		    int dlen = Math.min(nf.getPL(), level);
		    for (int j=0;j < dlen;j++){
			float pdist = pnt.getPathDistance(j);
			float tdist = targetdists.get(j);
			if (tdist < pdist - radius || tdist > pdist + radius){
			    includePoint = false;
			    break;
			}
		    }
		    if (includePoint){
			float distance = target.distance(pnt);
			if (distance <= radius){
			    addToList(pnt, results, qdists, distance);
			}
		    }
		}
		
	    }
	}
    }

    /** query the tree for a target datapoint.
     * @param target Datapoint to look for.
     * @param radius radius around point to look.
     * @return Iterable collection of datapoint results
     **/
    public Iterable<Datapoint> query(Datapoint target, float radius){
	ArrayList<Datapoint> results = new ArrayList<Datapoint>();
	ArrayList<Float> distances = new ArrayList<Float>();
	ArrayList<Float> qdists = new ArrayList<Float>();

	MVPNode topnode = nf.getTopNode();
	ArrayList<MVPNode> currentnodes = new ArrayList<MVPNode>();
	currentnodes.add(topnode);
	
	boolean done = true;
	int n = 0;
	do {
	    done = true;
	    ArrayList<MVPNode> childnodes = new ArrayList<MVPNode>();

	    int nodeIndex = 0;
	    for (MVPNode node : currentnodes){
		if (node != null){
		    checkNode(node, target, results, distances, qdists, radius, childnodes, n);
		} 
		nodeIndex++;
	    }

	    currentnodes = childnodes;
	    n = n+nf.getNL();

	    // check end condition
	    if (currentnodes.size() > 0){
		done = false;
	    }

	} while (!done);

	return results;
    }

    /**
     * clear the tree.
     **/
    public void clear(){
	MVPNode topnode = nf.getTopNode();
	ArrayList<MVPNode> currentnodes = new ArrayList<MVPNode>();
	currentnodes.add(topnode);
	
	nf.clearDatapointIndex();
	int n=0;
	int nlevels = nf.getNL();
	int bf = nf.getBF();
	boolean done = true;
	do {
	    done = true;
	    int nbchildnodes = (int)Math.pow(bf, n+nlevels);
	    ArrayList<MVPNode> childnodes = new ArrayList<MVPNode>(nbchildnodes);

	    for (MVPNode node : currentnodes){
		expandNode(node, childnodes);
		if (node != null){
		    if (node instanceof MVPInternal){
			ArrayList<Datapoint> vps = getVantagePoints((MVPInternal)node);
			for (Datapoint pnt : vps){
			    pnt.delete();
			}
		    }
		    if (node instanceof MVPLeaf){
			MVPLeaf leaf = (MVPLeaf)node;
			int nbpoints = leaf.getPointCount();
			for (int i=0;i<nbpoints;i++){
			    Datapoint pnt = leaf.getDatapoint(i,nf);
			    pnt.delete();
			}
		    }
		    node.delete();
		}
	    }
	    
	    currentnodes = childnodes;
	    n=n+nlevels;
	    
	    for (MVPNode node: currentnodes){
		if (node != null){
		    done = false;
		    break;
		}
	    }
	} while (!done);

    }

}